package com.sjc.algorithm.interview;

/**
 * 最大公约数
 * @author by SangJiacun
 * @Date 2020/5/13 22:20
 */
public class GreatestCommonDivisor {

    public static void main(String[] args) {
        System.out.println(getGreatestCommonDivisorV4(25,5));
        System.out.println(getGreatestCommonDivisorV4(100,80));
        System.out.println(getGreatestCommonDivisorV4(27,14));
    }

    /**
     * 辗转相除法
     * @param a
     * @param b
     * @return 最大公约数
     */
    private static int getGreatestCommonDivisorV2(int a,int b){
        int max = a>b?a:b;
        int min = a>b?b:a;
        if(max%min==0){
            return min;
        }
        return getGreatestCommonDivisorV2(max%min,min);
    }

    private static int getGreatestCommonDivisorV3(int a,int b){
        int max = a>b?a:b;
        int min = a>b?b:a;
        if(a == b){
            return min;
        }
        return getGreatestCommonDivisorV3(max-min,min);
    }

    private static int getGreatestCommonDivisorV4(int a,int b){
        if(a == b){
            return a;
        }

        boolean a1 = a%2==0;
        boolean b1 = b%2==0;

        if(a1 && b1){
            return getGreatestCommonDivisorV4(a>>1,b>>1)<<1;
        }else if(!a1 && b1){
            return getGreatestCommonDivisorV4(a,b>>1);
        }else if(a1 && !b1){
            return getGreatestCommonDivisorV4(a>>1,b);
        }else{
            int max = a>b?a:b;
            int min = a>b?b:a;
            return getGreatestCommonDivisorV4(max-min,min);
        }
    }
}
